package com.leetcode.根据数据结构分类.二叉树;

import com.leetcode.datastructure.TreeNode;

/**
 * @author: ZhouBert
 * @date: 2020/11/27
 * @description: 105. 从前序与中序遍历序列构造二叉树
 * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 */
public class B_105_从前序与中序遍历序列构造二叉树 {

	/**
	 * 这个错了
	 *
	 * @param preorder
	 * @param inorder
	 * @return
	 */
	public static TreeNode buildTree(int[] preorder, int[] inorder) {
		if (preorder.length == 0) {
			return null;
		}
//		TreeNode root = new TreeNode(preorder[0]);
//
//		int inRootindex = getIndex(inorder, 0, inorder.length - 1, preorder[0]);
//		int preLeftEnd = getIndex(preorder, 0, preorder.length - 1, inorder[inRootindex - 1]);
//		root.left = getNode(preorder, 1, preLeftEnd, inorder, 0, inRootindex - 1);
//		root.right = getNode(preorder, preLeftEnd + 1, preorder.length - 1, inorder, inRootindex + 1, inorder.length - 1);

		return getNode(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
	}

	/**
	 * 1.从该递归方法里找到根节点-> root
	 * 这个代码是由瑕疵的，于是放弃
	 *
	 * @param preorder
	 * @param preb
	 * @param pree
	 * @param inorder
	 * @param inb
	 * @param ine
	 * @return
	 */
	static TreeNode getNode(int[] preorder, int preb, int pree, int[] inorder, int inb, int ine) {

		//1.找到根节点
		TreeNode root = new TreeNode(preorder[preb]);
		int inRootIndex = getIndex(inorder, inb, ine, preorder[preb]);

		//如果左子树只有一个节点
		if (inRootIndex == inb + 1) {
			root.left = new TreeNode(inorder[inb]);
		} else if (inRootIndex == inb) {
			root.left = null;
		} else {
			int preLeftEnd = getIndex(preorder, preb, pree, inorder[inRootIndex - 1]);
			System.out.println("preb:" + (preb + 1) + " pree:" + preLeftEnd);
			System.out.println("inb:" + (inb) + " ine:" + (inRootIndex - 1));
			root.left = getNode(preorder, preb + 1, preLeftEnd, inorder, inb, inRootIndex - 1);
		}
		if (inRootIndex == ine - 1) {
			root.right = new TreeNode(inorder[ine]);
		} else if (inRootIndex == ine) {
			root.right = null;
		} else {
			int preLeftEnd = inb == inRootIndex ? inb : getIndex(preorder, preb, pree, inorder[inRootIndex - 1]);

			//int preRightBegin = getIndex(preorder, preb, pree, inorder[inRootIndex + 1]);
			root.right = getNode(preorder, preLeftEnd + 1, pree, inorder, inRootIndex + 1, ine);
		}
		return root;
	}

	static int getIndex(int[] arr, int begin, int end, int val) {
		for (int i = begin; i <= end; i++) {
			if (arr[i] == val) {
				return i;
			}
		}
		return -1;
	}


	/**
	 * @param preorder
	 * @param inorder
	 * @return
	 */
	public static TreeNode buildTree2(int[] preorder, int[] inorder) {
		if (preorder.length == 0) {
			return null;
		}

		return getNode2(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
	}

	/**
	 * 这个方法是为了去构造一棵完整的子树的，那么边界条件就是：
	 * 1.root==null
	 * 2.root 的度为0
	 * 【特殊考虑左子树没有右节点时】--> 说明需要通过长度来进行定位，而不是通过索引！
	 * 看来我的思路还是有Bug!!!
	 *
	 * @param preorder
	 * @param preB
	 * @param preE
	 * @param inorder
	 * @param inB
	 * @param inE
	 * @return
	 */
	private static TreeNode getNode2(int[] preorder, int preB, int preE, int[] inorder, int inB, int inE) {
		//边界条件1：root = null
		if (preB > preE || inB > inE) {
			return null;
		}
		TreeNode root = new TreeNode(preorder[preB]);
		//边界条件2
		if (preB == preE || inB == inE) {
			return root;
		}
		//进入递归
		//1.找到根节点
		int rootValue = preorder[preB];
		//2.找到 inorder 里的 根节点索引
		int inRootIndex = getIndex(inorder, rootValue);
		//3.找到 preorder 中 左节点的末尾 + 确认左子树
		if (inRootIndex == inB) {
			//此时说明没有 左子树
			root.left = null;
			//那么其余部分都是右子树！
			root.right = getNode2(preorder, preB + 1, preE, inorder, inRootIndex + 1, inE);
		} else {
			if (inRootIndex < inB) {
				throw new RuntimeException("!!");
			}
			int preLeftEnd = getIndex(preorder, inorder[inRootIndex - 1]);
			root.left = getNode2(preorder, preB + 1, preLeftEnd, inorder, inB, inE - 1);
			//4.确认右子树
			root.right = getNode2(preorder, preLeftEnd + 1, preE, inorder, inRootIndex + 1, inE);
		}

		return root;
	}

	static int getIndex(int[] arr, int val) {
		for (int i = 0; i <= arr.length; i++) {
			if (arr[i] == val) {
				return i;
			}
		}
		return -1;
	}


	/**
	 * 终于就是正解了！！！
	 * （可以构建一个 map ,用来快速定位 inorder 中 root 的索引）
	 * @param preorder
	 * @param preB
	 * @param preE
	 * @param inorder
	 * @param inB
	 * @param inE
	 * @return
	 */
	public static TreeNode getNode3(int[] preorder, int preB, int preE, int[] inorder, int inB, int inE) {
		//边界条件1：root = null
		if (preB > preE || inB > inE) {
			return null;
		}
		TreeNode root = new TreeNode(preorder[preB]);
		//边界条件2
		if (preB == preE || inB == inE) {
			return root;
		}
		int rootValue = preorder[preB];
		int inRootIndex = getIndex(inorder, rootValue);
		//左节点的个数
		int leftSize = inRootIndex - inB;
		root.left = getNode3(preorder, preB + 1, preB + leftSize, inorder, inB, inE - 1);
		root.right =getNode3(preorder, preB + leftSize + 1, preE, inorder, inRootIndex + 1, inE);
		return root;
	}


	public static void main(String[] args) {
		int[] preorder = new int[]{3, 9, 20, 15, 7};
//		preorder = new int[]{4, 2, 1, 3, 6, 5};
		//preorder = new int[]{-1};
//		preorder = new int[]{ 1, 2, 3};
		preorder = new int[]{4, 1, 2, 3};
		preorder = new int[]{1, 2};
		preorder = new int[]{1, 2, 3};
		int[] inorder = new int[]{9, 3, 15, 20, 7};
//		inorder = new int[]{1, 2, 3, 4, 5, 6};
		//inorder = new int[]{-1};
//		inorder  = new int[]{ 1, 2, 3};
		inorder = new int[]{1, 2, 3, 4};
		inorder = new int[]{1, 2};
		inorder = new int[]{3, 2, 1};
		TreeNode root = buildTree2(preorder, inorder);
		int a = 1;

	}
}
